package algorithm.middle;

import pojo.ListNode;



/**
 * @author 江岸
 * @version V1.0
 * @ClassName: ReverseBetween92
 * @description: 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/3/189:31
 * @since V1.0
 */
public class ReverseBetween92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode newNode = head;
        ListNode PreLink = null;
        ListNode postLink = null;
        //找到从哪里开始翻转
        for(int i=1;i<left;i++){
            PreLink = newNode;
            newNode = newNode.next;
        }
        //翻转链表的次数
        ListNode newHead = newNode;
        ListNode current=null;
        for (int i=right-left;i>-1;i--){
            current = newHead;
            newHead = newHead.next;
            current.next = postLink;
            postLink = current;
        }
        //左断点连结 翻转链表的头节点
        if (PreLink!=null){
            PreLink.next = postLink;
        }
        //翻转链表的尾节点 连结右断点
        newNode.next = newHead;
        //如果输入从左边第一个截取，则不能返回头节点，只能返回current节点
        return left==1?current:head;
    }
}
